package com.leetcode.algorithm.y21.m07;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * leetcode-cn.com
 * 滑动窗口
 * 219. 存在重复元素 II
 * 643. 子数组最大平均数 I
 * 1763. 最长的美好子字符串
 * 1876. 长度为三且各字符不同的子字符串
 * 3. 无重复字符的最长子串
 * 
 * @author jie.deng
 *
 */
public class MySolution0727 {
	
	/**
	 * 219. 存在重复元素 II
	 * 
	 * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
	 * 
	 *  
	 * 
	 * 示例 1:
	 * 
	 * 输入: nums = [1,2,3,1], k = 3
	 * 输出: true
	 * 示例 2:
	 * 
	 * 输入: nums = [1,0,1,1], k = 1
	 * 输出: true
	 * 示例 3:
	 * 
	 * 输入: nums = [1,2,3,1,2,3], k = 2
	 * 输出: false
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/contains-duplicate-ii
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * 
	 * @param nums
	 * @param k
	 * @return
	 */
	public boolean containsNearbyDuplicate(int[] nums, int k) {
		if (k == 0) {
			return false;
		}

		// numSet ：滑动窗口内nums[i]的集合
		Set<Integer> numSet = new HashSet<>();
		for (int i = 0; i < nums.length; i++) {
			if (!numSet.add(nums[i])) {
				return true;
			}
			if (numSet.size() > k) {
				numSet.remove(nums[i - k]);
			}
		}

		return false;
	}
    
    
    /**
     * 643. 子数组最大平均数 I
     * 
	 * 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
	 * 
	 *  
	 * 
	 * 示例：
	 * 
	 * 输入：[1,12,-5,-6,50,3], k = 4
	 * 输出：12.75
	 * 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= k <= n <= 30,000。
	 * 所给数据范围 [-10,000，10,000]。
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/maximum-average-subarray-i
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param nums
     * @param k
     * @return
     */
	public double findMaxAverage(int[] nums, int k) {
		double maxSum = 0;
		double sum = 0;
		for (int i = 0; i < k; i++) {
			sum += nums[i];
		}
		maxSum = sum;

		for (int i = k; i < nums.length; i++) {
			sum += nums[i];
			sum -= nums[i - k];
			maxSum = Math.max(sum, maxSum);
		}

		return maxSum / k;
	}
    
    
    /**
     * 1763. 最长的美好子字符串
     * 
     * 
	 * 当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。
	 * 
	 * 给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：s = "YazaAay"
	 * 输出："aAa"
	 * 解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
	 * "aAa" 是最长的美好子字符串。
	 * 示例 2：
	 * 
	 * 输入：s = "Bb"
	 * 输出："Bb"
	 * 解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。
	 * 示例 3：
	 * 
	 * 输入：s = "c"
	 * 输出：""
	 * 解释：没有美好子字符串。
	 * 示例 4：
	 * 
	 * 输入：s = "dDzeE"
	 * 输出："dD"
	 * 解释："dD" 和 "eE" 都是最长美好子字符串。
	 * 由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= s.length <= 100
	 * s 只包含大写和小写英文字母。
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/longest-nice-substring
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param s
     * @return
     */
	public String longestNiceSubstring(String s) {
		// 暴力窗口O(n*n*n)
		for (int winSize = s.length(); winSize >= 2; winSize--) {
			for (int winBeginIdx = 0; winBeginIdx + winSize - 1 < s.length(); winBeginIdx++) {
				if (isNiceSubstring(s, winBeginIdx, winBeginIdx + winSize)) {
					return s.substring(winBeginIdx, winBeginIdx + winSize);
				}
			}
		}
		return "";
	}
    
	private boolean isNiceSubstring(String s, int beginIndex, int endIndex) {
		boolean[] lowerCaseArr = new boolean[26];
		boolean[] upperCaseArr = new boolean[26];
		for (int i = beginIndex; i < endIndex; i++) {
			char ch = s.charAt(i);
			if (ch >= 'a' && ch <= 'z') {
				lowerCaseArr[ch - 'a'] = true;
			} else {
				upperCaseArr[ch - 'A'] = true;
			}
		}
		for (int i = 0; i < upperCaseArr.length; i++) {
			if (lowerCaseArr[i] != upperCaseArr[i]) {
				return false;
			}
		}
		return true;
	}


	/**
     * 1876. 长度为三且各字符不同的子字符串
     * 
	 * 如果一个字符串不含有任何重复字符，我们称这个字符串为 好 字符串。
	 * 
	 * 给你一个字符串 s ，请你返回 s 中长度为 3 的 好子字符串 的数量。
	 * 
	 * 注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。
	 * 
	 * 子字符串 是一个字符串中连续的字符序列。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：s = "xyzzaz"
	 * 输出：1
	 * 解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。
	 * 唯一的长度为 3 的好子字符串是 "xyz" 。
	 * 示例 2：
	 * 
	 * 输入：s = "aababcabc"
	 * 输出：4
	 * 解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。
	 * 好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= s.length <= 100
	 * s​​​​​​ 只包含小写英文字母。
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/substrings-of-size-three-with-distinct-characters
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param s
     * @return
     */
	public int countGoodSubstrings(String s) {
		int cnt = 0;
		int midIdx = 1;
		while (midIdx < s.length() - 1) {
			if (s.charAt(midIdx) == s.charAt(midIdx + 1)) {
				midIdx += 1;
			} else {
				if (s.charAt(midIdx) != s.charAt(midIdx - 1) && s.charAt(midIdx + 1) != s.charAt(midIdx - 1)) {
					cnt += 1;
				}
			}
			midIdx += 1;
		}

		return cnt;
	}
    
    /**
     * 3. 无重复字符的最长子串
     * 
     * 
	 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
	 * 
	 *  
	 * 
	 * 示例 1:
	 * 
	 * 输入: s = "abcabcbb"
	 * 输出: 3 
	 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
	 * 示例 2:
	 * 
	 * 输入: s = "bbbbb"
	 * 输出: 1
	 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
	 * 示例 3:
	 * 
	 * 输入: s = "pwwkew"
	 * 输出: 3
	 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
	 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
	 * 示例 4:
	 * 
	 * 输入: s = ""
	 * 输出: 0
	 *  
	 * 
	 * 提示：
	 * 
	 * 0 <= s.length <= 5 * 104
	 * s 由英文字母、数字、符号和空格组成
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
    	// Step 1: 定义需要维护的变量
    	// maxLen ：最长子串的长度
		int maxLen = 0;
		// cntMap<K,V> ：滑动窗口内字符K出现的次数V
		Map<Character, Integer> cntMap = new HashMap<>();
		
		// Step 2: 定义窗口的首尾端 (left, right)， 然后滑动窗口
		int left = 0;
		for (int right = 0; right < s.length(); right++) {
			// Step 3: 滑动窗口右索引改变前，更新需要维护的变量
			Character ch = Character.valueOf(s.charAt(right));
			Integer cnt = cntMap.get(ch);
			cntMap.put(ch, cnt == null ? 1 : cnt.intValue() + 1);
			if (right - left + 1 == cntMap.size()) {
				maxLen = Math.max(maxLen, right - left + 1);
			}
			
			// Step 4: 当前滑动窗口不满足条件，需要改变左索引
			while (left < right && right - left + 1 != cntMap.size()) {
				// 滑动窗口左索引改变前，更新需要维护的变量
				Character chL = Character.valueOf(s.charAt(left));
				Integer cntL = cntMap.get(chL);
				if (cntL == 1) {
					cntMap.remove(chL);
				} else {
					cntMap.put(chL, cntL.intValue() - 1);
				}
				
				left++;
			}
		}
    	
		// Step 5: 返回答案
		return maxLen;
    }
}
